
%% bare_jrnl.tex
%% V1.4
%% 2012/12/27
%% by Michael Shell
%% see http://www.michaelshell.org/
%% for current contact information.
%%
%% This is a skeleton file demonstrating the use of IEEEtran.cls
%% (requires IEEEtran.cls version 1.8 or later) with an IEEE journal paper.
%%
%% Support sites:
%% http://www.michaelshell.org/tex/ieeetran/
%% http://www.ctan.org/tex-archive/macros/latex/contrib/IEEEtran/
%% and
%% http://www.ieee.org/



% *** Authors should verify (and, if needed, correct) their LaTeX system ***
% *** with the testflow diagnostic prior to trusting their LaTeX platform ***
% *** with production work. IEEE's font choices can trigger bugs that do ***
% *** not appear when using other class files. ***
% The testflow support page is at:
% http://www.michaelshell.org/tex/testflow/


%%*************************************************************************
%% Legal Notice:
%% This code is offered as-is without any warranty either expressed or
%% implied; without even the implied warranty of MERCHANTABILITY or
%% FITNESS FOR A PARTICULAR PURPOSE!
%% User assumes all risk.
%% In no event shall IEEE or any contributor to this code be liable for
%% any damages or losses, including, but not limited to, incidental,
%% consequential, or any other damages, resulting from the use or misuse
%% of any information contained here.
%%
%% All comments are the opinions of their respective authors and are not
%% necessarily endorsed by the IEEE.
%%
%% This work is distributed under the LaTeX Project Public License (LPPL)
%% ( http://www.latex-project.org/ ) version 1.3, and may be freely used,
%% distributed and modified. A copy of the LPPL, version 1.3, is included
%% in the base LaTeX documentation of all distributions of LaTeX released
%% 2003/12/01 or later.
%% Retain all contribution notices and credits.
%% ** Modified files should be clearly indicated as such, including **
%% ** renaming them and changing author support contact information. **
%%
%% File list of work: IEEEtran.cls, IEEEtran_HOWTO.pdf, bare_adv.tex,
%% bare_conf.tex, bare_jrnl.tex, bare_jrnl_compsoc.tex,
%% bare_jrnl_transmag.tex
%%*************************************************************************

% Note that the a4paper option is mainly intended so that authors in
% countries using A4 can easily print to A4 and see how their papers will
% look in print - the typesetting of the document will not typically be
% affected with changes in paper size (but the bottom and side margins will).
% Use the testflow package mentioned above to verify correct handling of
% both paper sizes by the user's LaTeX system.
%
% Also note that the "draftcls" or "draftclsnofoot", not "draft", option
% should be used if it is desired that the figures are to be displayed in
% draft mode.
%
\documentclass[journal]{IEEEtran}
%
% If IEEEtran.cls has not been installed into the LaTeX system files,
% manually specify the path to it like:
% \documentclass[journal]{../sty/IEEEtran}





% Some very useful LaTeX packages include:
% (uncomment the ones you want to load)


% *** MISC UTILITY PACKAGES ***
%
%\usepackage{ifpdf}
% Heiko Oberdiek's ifpdf.sty is very useful if you need conditional
% compilation based on whether the output is pdf or dvi.
% usage:
% \ifpdf
% % pdf code
% \else
% % dvi code
% \fi
% The latest version of ifpdf.sty can be obtained from:
% http://www.ctan.org/tex-archive/macros/latex/contrib/oberdiek/
% Also, note that IEEEtran.cls V1.7 and later provides a builtin
% \ifCLASSINFOpdf conditional that works the same way.
% When switching from latex to pdflatex and vice-versa, the compiler may
% have to be run twice to clear warning/error messages.






% *** CITATION PACKAGES ***
%
\usepackage{cite}
% cite.sty was written by Donald Arseneau
% V1.6 and later of IEEEtran pre-defines the format of the cite.sty package
% \cite{} output to follow that of IEEE. Loading the cite package will
% result in citation numbers being automatically sorted and properly
% "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using
% cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's
% \cite will automatically add leading space, if needed. Use cite.sty's
% noadjust option (cite.sty V3.8 and later) if you want to turn this off
% such as if a citation ever needs to be enclosed in parenthesis.
% cite.sty is already installed on most LaTeX systems. Be sure and use
% version 4.0 (2003-05-27) and later if using hyperref.sty. cite.sty does
% not currently provide for hyperlinked citations.
% The latest version can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/cite/
% The documentation is contained in the cite.sty file itself.






% *** GRAPHICS RELATED PACKAGES ***
%
\ifCLASSINFOpdf
% \usepackage[pdftex]{graphicx}
% declare the path(s) where your graphic files are
% \graphicspath{{../pdf/}{../jpeg/}}
% and their extensions so you won't have to specify these with
% every instance of \includegraphics
% \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
\else
% or other class option (dvipsone, dvipdf, if not using dvips). graphicx
% will default to the driver specified in the system graphics.cfg if no
% driver is specified.
% \usepackage[dvips]{graphicx}
% declare the path(s) where your graphic files are
% \graphicspath{{../eps/}}
% and their extensions so you won't have to specify these with
% every instance of \includegraphics
% \DeclareGraphicsExtensions{.eps}
\fi
% graphicx was written by David Carlisle and Sebastian Rahtz. It is
% required if you want graphics, photos, etc. graphicx.sty is already
% installed on most LaTeX systems. The latest version and documentation
% can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/graphics/
% Another good source of documentation is "Using Imported Graphics in
% LaTeX2e" by Keith Reckdahl which can be found at:
% http://www.ctan.org/tex-archive/info/epslatex/
%
% latex, and pdflatex in dvi mode, support graphics in encapsulated
% postscript (.eps) format. pdflatex in pdf mode supports graphics
% in .pdf, .jpeg, .png and .mps (metapost) formats. Users should ensure
% that all non-photo figures use a vector format (.eps, .pdf, .mps) and
% not a bitmapped formats (.jpeg, .png). IEEE frowns on bitmapped formats
% which can result in "jaggedy"/blurry rendering of lines and letters as
% well as large increases in file sizes.
%
% You can find documentation about the pdfTeX application at:
% http://www.tug.org/applications/pdftex





% *** MATH PACKAGES ***
%
%\usepackage[cmex10]{amsmath}
% A popular package from the American Mathematical Society that provides
% many useful and powerful commands for dealing with mathematics. If using
% it, be sure to load this package with the cmex10 option to ensure that
% only type 1 fonts will utilized at all point sizes. Without this option,
% it is possible that some math symbols, particularly those within
% footnotes, will be rendered in bitmap form which will result in a
% document that can not be IEEE Xplore compliant!
%
% Also, note that the amsmath package sets \interdisplaylinepenalty to 10000
% thus preventing page breaks from occurring within multiline equations. Use:
%\interdisplaylinepenalty=2500
% after loading amsmath to restore such page breaks as IEEEtran.cls normally
% does. amsmath.sty is already installed on most LaTeX systems. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/amslatex/math/





% *** SPECIALIZED LIST PACKAGES ***
%
%\usepackage{algorithmic}
% algorithmic.sty was written by Peter Williams and Rogerio Brito.
% This package provides an algorithmic environment fo describing algorithms.
% You can use the algorithmic environment in-text or within a figure
% environment to provide for a floating algorithm. Do NOT use the algorithm
% floating environment provided by algorithm.sty (by the same authors) or
% algorithm2e.sty (by Christophe Fiorio) as IEEE does not use dedicated
% algorithm float types and packages that provide these will not provide
% correct IEEE style captions. The latest version and documentation of
% algorithmic.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithms/
% There is also a support site at:
% http://algorithms.berlios.de/index.html
% Also of interest may be the (relatively newer and more customizable)
% algorithmicx.sty package by Szasz Janos:
% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithmicx/




% *** ALIGNMENT PACKAGES ***
%
%\usepackage{array}
% Frank Mittelbach's and David Carlisle's array.sty patches and improves
% the standard LaTeX2e array and tabular environments to provide better
% appearance and additional user controls. As the default LaTeX2e table
% generation code is lacking to the point of almost being broken with
% respect to the quality of the end results, all users are strongly
% advised to use an enhanced (at the very least that provided by array.sty)
% set of table tools. array.sty is already installed on most systems. The
% latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/tools/


% IEEEtran contains the IEEEeqnarray family of commands that can be used to
% generate multiline equations as well as matrices, tables, etc., of high
% quality.




% *** SUBFIGURE PACKAGES ***
%\ifCLASSOPTIONcompsoc
% \usepackage[caption=false,font=normalsize,labelfont=sf,textfont=sf]{subfig}
%\else
% \usepackage[caption=false,font=footnotesize]{subfig}
%\fi
% subfig.sty, written by Steven Douglas Cochran, is the modern replacement
% for subfigure.sty, the latter of which is no longer maintained and is
% incompatible with some LaTeX packages including fixltx2e. However,
% subfig.sty requires and automatically loads Axel Sommerfeldt's caption.sty
% which will override IEEEtran.cls' handling of captions and this will result
% in non-IEEE style figure/table captions. To prevent this problem, be sure
% and invoke subfig.sty's "caption=false" package option (available since
% subfig.sty version 1.3, 2005/06/28) as this is will preserve IEEEtran.cls
% handling of captions.
% Note that the Computer Society format requires a larger sans serif font
% than the serif footnote size font used in traditional IEEE formatting
% and thus the need to invoke different subfig.sty package options depending
% on whether compsoc mode has been enabled.
%
% The latest version and documentation of subfig.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/subfig/




% *** FLOAT PACKAGES ***
%
%\usepackage{fixltx2e}
% fixltx2e, the successor to the earlier fix2col.sty, was written by
% Frank Mittelbach and David Carlisle. This package corrects a few problems
% in the LaTeX2e kernel, the most notable of which is that in current
% LaTeX2e releases, the ordering of single and double column floats is not
% guaranteed to be preserved. Thus, an unpatched LaTeX2e can allow a
% single column figure to be placed prior to an earlier double column
% figure. The latest version and documentation can be found at:
% http://www.ctan.org/tex-archive/macros/latex/base/


%\usepackage{stfloats}
% stfloats.sty was written by Sigitas Tolusis. This package gives LaTeX2e
% the ability to do double column floats at the bottom of the page as well
% as the top. (e.g., "\begin{figure*}[!b]" is not normally possible in
% LaTeX2e). It also provides a command:
%\fnbelowfloat
% to enable the placement of footnotes below bottom floats (the standard
% LaTeX2e kernel puts them above bottom floats). This is an invasive package
% which rewrites many portions of the LaTeX2e float routines. It may not work
% with other packages that modify the LaTeX2e float routines. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/sttools/
% Do not use the stfloats baselinefloat ability as IEEE does not allow
% \baselineskip to stretch. Authors submitting work to the IEEE should note
% that IEEE rarely uses double column equations and that authors should try
% to avoid such use. Do not be tempted to use the cuted.sty or midfloat.sty
% packages (also by Sigitas Tolusis) as IEEE does not format its papers in
% such ways.
% Do not attempt to use stfloats with fixltx2e as they are incompatible.
% Instead, use Morten Hogholm'a dblfloatfix which combines the features
% of both fixltx2e and stfloats:
%
% \usepackage{dblfloatfix}
% The latest version can be found at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/dblfloatfix/




%\ifCLASSOPTIONcaptionsoff
% \usepackage[nomarkers]{endfloat}
% \let\MYoriglatexcaption\caption
% \renewcommand{\caption}[2][\relax]{\MYoriglatexcaption[#2]{#2}}
%\fi
% endfloat.sty was written by James Darrell McCauley, Jeff Goldberg and
% Axel Sommerfeldt. This package may be useful when used in conjunction with
% IEEEtran.cls' captionsoff option. Some IEEE journals/societies require that
% submissions have lists of figures/tables at the end of the paper and that
% figures/tables without any captions are placed on a page by themselves at
% the end of the document. If needed, the draftcls IEEEtran class option or
% \CLASSINPUTbaselinestretch interface can be used to increase the line
% spacing as well. Be sure and use the nomarkers option of endfloat to
% prevent endfloat from "marking" where the figures would have been placed
% in the text. The two hack lines of code above are a slight modification of
% that suggested by in the endfloat docs (section 8.4.1) to ensure that
% the full captions always appear in the list of figures/tables - even if
% the user used the short optional argument of \caption[]{}.
% IEEE papers do not typically make use of \caption[]'s optional argument,
% so this should not be an issue. A similar trick can be used to disable
% captions of packages such as subfig.sty that lack options to turn off
% the subcaptions:
% For subfig.sty:
% \let\MYorigsubfloat\subfloat
% \renewcommand{\subfloat}[2][\relax]{\MYorigsubfloat[]{#2}}
% However, the above trick will not work if both optional arguments of
% the \subfloat command are used. Furthermore, there needs to be a
% description of each subfigure *somewhere* and endfloat does not add
% subfigure captions to its list of figures. Thus, the best approach is to
% avoid the use of subfigure captions (many IEEE journals avoid them anyway)
% and instead reference/explain all the subfigures within the main caption.
% The latest version of endfloat.sty and its documentation can obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/endfloat/
%
% The IEEEtran \ifCLASSOPTIONcaptionsoff conditional can also be used
% later in the document, say, to conditionally put the References on a
% page by themselves.




% *** PDF, URL AND HYPERLINK PACKAGES ***
%
%\usepackage{url}
% url.sty was written by Donald Arseneau. It provides better support for
% handling and breaking URLs. url.sty is already installed on most LaTeX
% systems. The latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/url/
% Basically, \url{my_url_here}.


% *** Do not adjust lengths that control margins, column widths, etc. ***
% *** Do not use packages that alter fonts (such as pslatex). ***
% There should be no need to do such things with IEEEtran.cls V1.6 and later.
% (Unless specifically asked to do so by the journal or conference you plan
% to submit to, of course. )


% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}


% ** LUKE AND BRENDAN PACKAGES **

\usepackage{fixltx2e}
\usepackage{pdfpages}


\begin{document}
%
% paper title
% can use linebreaks \\ within to get better formatting as desired
% Do not put math or special symbols in the title.
\title{Blinded, Accountable Mixes for Bitcoin}
%
%
% author names and IEEE memberships
% note positions of commas and nonbreaking spaces ( ~ ) LaTeX will not break
% a structure at a ~ so this keeps an author's name from being broken across
% two lines.
% use \thanks{} to gain access to the first footnote area
% a separate \thanks must be used for each paragraph as LaTeX2e's \thanks
% was not built to handle multiple paragraphs
%

\author{Luke~Valenta, Brendan~Rowan\\May~18,~2014}% <-this % stops a space


% make the title area
\maketitle


% As a general rule, do not put math, special symbols or citations
% in the abstract or keywords.
\begin{abstract}

We propose modifications to the Bitcoin mixing system {\sl Mixcoin} \cite{mixcoin} that allow the mix to be blinded to the mapping between a particular user's input/output addresses, all while maintaining the accountability guarantees provided by the {\sl Mixcoin} system. In order to acheive this, we make use of Chaum's signature blinding scheme \cite{chaum} as well as a public log as proposed in \cite{multiparty}.

\end{abstract}






% For peer review papers, you can put extra information on the cover
% page as needed:
% \ifCLASSOPTIONpeerreview
% \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
% \fi
%
% For peerreview papers, this IEEEtran command inserts a page break and
% creates the second title. It will be ignored for other modes.
\IEEEpeerreviewmaketitle



%-------------------------------------------------------------------------------
\section{Introduction}

\IEEEPARstart{R}{ecently}, many systems have been proposed to serve as Bitcoin mixing services. These services allow users to exchange their coins for another user's coins randomly, such that the user attains anonymity within the set of users participating in the exchange. Properties that an ideal system should offer include the following:
\begin{itemize}
\item {\sl Accountability}. A user should be able to have a guarantee that their coins will not be stolen during the exchange process.
\item {\sl Anonymity}. The addresses a user provides for inputs to the mix should not be linkable to the addresses that the user provides for their outputs by any other party.
\item {\sl Resilience}. The system should not be vulnerable to attacks by a small number of malicious parties that could potentially DoS the exchange \cite{coinjoin},\cite{multiparty}.
\item {\sl Scalability}. The system should be able to scale to accomidate for large anonymity sets.
\item {\sl Incentivized}. There should be a mechanism for the mix to collect mixing fees fairly that will incentivize it to provide the service.
\item {\sl Compatibility}. The system should be compatible with the current Bitcoin system.
\end{itemize}

Our proposed system meets all of the above goals. For accountability, we use a warranty scheme that allows the user to provide evidence against the mix if it misbehaves, similar to \cite{mixcoin}. Anonymity is provided by using Chaum's blinded signature scheme to hide the output addresses of a transaction. The user then connects anonymously to unblind their output address. The system also is resilient to DoS attacks by a single user refusing to sign a joint transaction, as certain schemes are susceptible to \cite{coinjoin}, \cite{multiparty}. This is possible since the mix deals with each user individually, and can exclude users from the exchange on a case-by-case basis. Finally, the system is scalable since it does not require any computationally complex encryption as do some other systems \cite{multiparty}.

Our system is based on the {\sl Mixcoin} system and draws many of its ideas from it. We assume the reader is familiar with this protocol, since our proposed protocol is based off of it. The main modifications that we make are the introduction of an append-only public log, {\sl PL}, that is used to keep the mix accountable; the utilization of a commutative encryption scheme to hide from the mix the mapping between a user's input and output addresses; and the requirement that the mix must decide on the public parameters for any given exchange, rather than the user choosing the terms as is the case in Mixcoin. We discuss the advantages and drawbacks of the additional steps that are required throughout the paper.
%-------------------------------------------------------------------------------
\section{Background and Related Work}

\subsection{Mixcoin}
Mixcoin is a protocol that requires no alterations to Bitcoin and intends to allow users to send coins anonymously.  It offers a cryptographic warranty that the server will send coins to the user’s output address, so that any user can incriminate the server if it does not comply.  However, Mixcoin is centralized, so the server can link users’ input and output addresses.

\subsection{CoinJoin/CoinShuffle}
CoinJoin is a decentralized protocol in which all users must sign a joint transaction \cite{coinjoin}. Users remain anonymous and their funds cannot be stolen, since a user will only provide its signature if they agree to the transaction. CoinJoin is vulnerable to a DoS by a single user if they refuse to provide a signature during the signing round of the protocol. The protocol CoinShuffle is built on CoinJoin. It ensures that a transaction will eventually go through by including a blaming process in which misbehaving users can be eliminated from future mixing attempts by the honest participants \cite{coinshuffle}.

\subsection{Secure multiparty sort}
Some schemes have been devised that use a form of secure multiparty sort to achieve anonymous mixing \cite{multiparty}.  Users provide an input address and an output address.  The input addresses and output addresses are sorted separately using the secure multiparty sort, a decentralized sorting algorithm.  Each input address will have a corresponding output address of another user, defined as the output address at the same index of the input address in the sorted lists.  Since there is a one-to-one relationship between input addresses and output addresses, each user sends a chuck size of bitcoins from their input address to the corresponding output address in the sorted list.  However, this is still vulnerable to a DoS by a single user, as a user can join but not send the chuck size of bitcoins.

%-------------------------------------------------------------------------------
\section{Model}
Our system runs under the same assumptions as the {\sl Mixcoin} protocol, except we add another entity, the public log. The list below summarizes the entities present in the system.
\begin{enumerate}
\item The public mix, {\sl M}, is assumed to have a long standing public key $K_M$. The model assumes that there are many such mixes that will compete, and the ones that have poor reputations will not be chosen by users. Thus, a mix is incentivized to participate in the protocol without allowing any proof of cheating to be made public.
%
\item The user, {\sl A}, which connects anonymously (using Tor, for example \cite{tor}).
%
\item An append-only public log that both users and the mix may post to. Each new mixing protocol should use a unique public log. The log includes a timestamp for each message that is posted to it. It is also assumed that no messages can be deleted from the log until after the round of mixing has completed. The introduction of this public log is the main way in which our model differs from that of Mixcoin.
\end{enumerate}
%

%-------------------------------------------------------------------------------
\section{Protocol}
In this section, we describe the protocol in further detail. The figure below accompanies the steps.
%
\begin{enumerate}
%
\item[0)] A mix $M$ publishes a set of {\sl mix data}, $D$, that users can view publicly. This data includes times ($t_1$,~$t_2$,~$t_3$,~$t_4$) by which different steps of the protocol must be completed; the chunk size, $v$, which is the number of coins that each user inputs into the transaction; $\rho$, the fraction of user inputs that will be kept as a mixing fee; $N$, a nonce which serves as the redundancy checking predicate described in \cite{chaum}; $w$, the number of blocks that the mix requires to verify the user’s payments. All of these parameters are part of the original Mixcoin protocol, except we add additional times $t_3$ and $t_4$ and the nonce $N$. We also require that the mix must define these terms, rather than the user. We explain why these changes are necessary in the Design Choices section.
%
\item[1)] A user $A$ opts in to the mix by sending its {\sl offer} to $M$. The offer includes the mix data for the mix that it wishes to participate in, followed by a privately selected nonce $n$, the public nonce $N$, and an ouptut address $k_{out}$, all of which are blinded by a commutative encryption function $C_A$ known only to $A$ (who also knows the inverse $C_A^{\prime}$). The offer has the following form: $\{D, [k_{out}, n, N]_{C_{A}}\}$.
%
\item[2a)] If the mix accepts the offer, it sends a {\sl partial warranty} back to the user, which consists of the signed (with the secret key of the mix) offer, as well as an escrow address $k_{esc}$ for the user to pay to. The reply has the form $[k_{esc}, [k_{out}, n, N]_{C_{A}}]_{K_{M}}$.
%
\item[2b)] If the mix rejects the offer, the user destroys the output address.
%
\item[3a)] The user then transfers v coins from any input address $k_{in}$ to the escrow address by time $t_{1}$.
%
\item[3b)] If the user fails to transer the funds on time, then both parties abort the protocol.
%
\item[4a)] Once the user has transferred the funds, $M$ must {\sl complete the warranty} by publishing tokens of the form $[[k_{out}, n, N]_{C_{A}}]_{K_{M}}$ to the public log by time $t_{2}$ (which should be long enough after $t_1$ to allow the transaction to be at least $w$ blocks deep into the chain). All users participating in the mix can find their token in the public log by decrypting tokens with the public key of $M$ until they find their blinded output address. The mix could also individually send each user back their signed token. However, it is important that the token is posted to the public log because this allows other parties to verify if/when a token was posted, to check that the mix obeyed the protocol and posted the tokens by time $t_2$.
%
\item[4b)] If $M$ fails to publish $A$'s token by $t_{2}$, $A$ can publish information to incriminate $M$ publicly. User $A$ can present the following evidence: the signed offer $[k_{esc},~[k_{out},~n, N]_{C_{A}}]_{K_{M}}$; the commutative encryption function $C_{A}$ and its inverse ${C^{\prime}_{A}}$; the fact that no token $[[k_{out},~n,~N]_{C_{A}}]_{K_{M}}$ was published to the public log before $t_2$; the transaction $Transfer(v,~k_{in},~k_{esc})$ present in the block chain before time $t_1$, along with proof that $A$ owns $k_{in}$. Any third party verifier can decrypt the signed offer with the public key of the mix, remove the commutative encryption using ${C^{\prime}_{A}}$, and verify that indeed no token of the correct form was published to the public log on time.
%
\item[5)] Now, $A$ applies $C_{A}^{\prime}$ to the token to remove the commutative layer of encryption, resulting in $[k_{out}, n, N]_{K_{M}}$. Then, the user connects anonymously as user $A^{\prime}$ and unblinds $k_{out}$ by posting the message \{$k_{out}, n, [k_{out}, N, n]_{K_{M}}$\} to the public log. The mix $M$ knows that the output address is valid, since it has been signed by the private key of the mix and includes the public nonce $N$ within it when decrypted using $M$'s public key. If $A$ fails to publish the unblinded signature to the public log by time $t_{3}$, $M$ can choose to either refund the coins back to $A$ or retain them. Since $A$ breached the protocol, it cannot produce evidence to incriminate $M$, so $M$ can do as it pleases with the funds.
%
\item[*] At this point, $M$ computes the beacon function $Beacon(t_3, w, n)$ for each $[k_{out}, n]$ pair to determine which output addresses to collect mixing fees from (by not sending any coins to them). The beacon function is described in the Mixcoin paper, but is basically a publicly verifiable function that uses entropy collected from the block chain to produce a number uniformly in the range $[0, 1]$. Then, if the value for a particular pair is less that or equal to the value $\rho$ defined in the mix data, the chunk destined for that output address is kept by $M$ as a mixing fee. Otherwise, the protocol proceeds to the next step.
%
\item[6a)] If $M$ acts honestly, it will transfer funds to all unblinded output addresses that have passed the $Beacon$ function by time $t_4$. The mix does not know which input and output addresses are from the same user, so the mapping from input to output addresses should not matter.
%
\item[6b)] $M$ steals the funds and fails to transfer a chunk to each of the output addresses by time $t_4$.

\item[7)] The user $A$ detects the theft at time $t_4$ (since no funds were transferred to its output address). User $A$ can present the following evidence: the signed offer $[k_{esc},~[k_{out},~n, N]_{C_{A}}]_{K_{M}}$; the commutative encryption function $C_{A}$ and its inverse ${C^{\prime}_{A}}$; the token $[[k_{out},~n,~N]_{C_{A}}]_{K_{M}}$ from the public log; the transaction $Transfer(v,~k_{in},~k_{esc})$ present in the block chain before time $t_1$, along with proof that $A$ owns $k_{in}$; and the fact that no such transaction $Transfer(v,~k^{\prime}_{out},~k_{out})$ is present in the block chain before time $t_4$.
Any third party verifier can decrypt the signed offer and the token with the public key of the mix and remove the commutative encryption using ${C^{\prime}_{A}}$. Then, the verifier can check the public log and the block chain to see if both parties followed the protocol.
%
\end{enumerate}


\section{Design Choices}
In this section, we discuss the modifications to the Mixcoin protocol that we made and our reasons for these changes.
\begin{itemize}
%
\item A commutative encryption function and its inverse that is known only to the user must be used to blind a user's output address in their original offer to the mix. The user later unblinds the output address anonymously.
%
\item An append-only public log must be used for third party verification purposes. If a party breaches protocol, the public log will contain enough information to incriminate the misbehaving party. The log will also be the party responsible for maintaining a clock to which all other parties must be synchronized. To prevent a party from flooding the log with bogus messages, a scheme could be set up to distribute blinded tokens that can be cashed in to post.
%
\item The mix must be the party that defines tthe {\sl mix data}. The reason for this is so that each user participating in the mix will have the same values for these parameters. Otherwise, if the user had to define these values, the mix could easily link together a single user's input and output addresses by looking at the values used.
%
\item The times $(t_1, t_2, t_3, t_4)$ must be agreed upon by all mix participants and the protocol steps should be carried out within the appropriate time intervals. This will help to prevent timing analysis attacks in which a single user's interactions with the mix are all clustered together in a short period of time. Furthermore, users should not make their interactions with the mix predictable. For example, if the mix reveals a particular token and then an output address is unblinded immediately afterwards, the mix may be able to link the token to the output address.
%
\end{itemize}

% An example of a floating figure using the graphicx package.
% Note that \label must occur AFTER (or within) \caption.
% For figures, \caption should occur after the \includegraphics.
% Note that IEEEtran v1.7 and later has special internal code that
% is designed to preserve the operation of \label within \caption
% even when the captionsoff option is in effect. However, because
% of issues like this, it may be the safest practice to put all your
% \label just after \caption rather than within \caption{}.
%
% Reminder: the "draftcls" or "draftclsnofoot", not "draft", class
% option should be used if it is desired that the figures are to be
% displayed while in draft mode.
%
%\begin{figure}[!t]
%\centering
%\includegraphics[width=2.5in]{myfigure}
% where an .eps filename suffix will be assumed under latex,
% and a .pdf suffix will be assumed for pdflatex; or what has been declared
% via \DeclareGraphicsExtensions.
%\caption{Simulation Results.}
%\label{fig_sim}
%\end{figure}

% Note that IEEE typically puts floats only at the top, even when this
% results in a large percentage of a column being occupied by floats.


% An example of a double column floating figure using two subfigures.
% (The subfig.sty package must be loaded for this to work.)
% The subfigure \label commands are set within each subfloat command,
% and the \label for the overall figure must come after \caption.
% \hfil is used as a separator to get equal spacing.
% Watch out that the combined width of all the subfigures on a
% line do not exceed the text width or a line break will occur.
%
%\begin{figure*}[!t]
%\centering
%\subfloat[Case I]{\includegraphics[width=2.5in]{box}%
%\label{fig_first_case}}
%\hfil
%\subfloat[Case II]{\includegraphics[width=2.5in]{box}%
%\label{fig_second_case}}
%\caption{Simulation results.}
%\label{fig_sim}
%\end{figure*}
%
% Note that often IEEE papers with subfigures do not employ subfigure
% captions (using the optional argument to \subfloat[]), but instead will
% reference/describe all of them (a), (b), etc., within the main caption.


% An example of a floating table. Note that, for IEEE style tables, the
% \caption command should come BEFORE the table. Table text will default to
% \footnotesize as IEEE normally uses this smaller font for tables.
% The \label must come after \caption as always.
%
%\begin{table}[!t]
%% increase table row spacing, adjust to taste
%\renewcommand{\arraystretch}{1.3}
% if using array.sty, it might be a good idea to tweak the value of
% \extrarowheight as needed to properly center the text within the cells
%\caption{An Example of a Table}
%\label{table_example}
%\centering
%% Some packages, such as MDW tools, offer better commands for making tables
%% than the plain LaTeX2e tabular which is used here.
%\begin{tabular}{|c||c|}
%\hline
%One & Two\\
%\hline
%Three & Four\\
%\hline
%\end{tabular}
%\end{table}


% Note that IEEE does not put floats in the very first column - or typically
% anywhere on the first page for that matter. Also, in-text middle ("here")
% positioning is not used. Most IEEE journals use top floats exclusively.
% Note that, LaTeX2e, unlike IEEE journals, places footnotes above bottom
% floats. This can be corrected via the \fnbelowfloat command of the
% stfloats package.



\section{Conclusion}
In this paper, we present a mixing system in which the mix is incentivized, blinded, and accountable. Furthermore, the system is not vulnerable to denial of service attacks caused by a single user refusing to sign a joint transaction. The system modifies the Mixcoin \cite{mixcoin} mixing protocol by using blinded signatures \cite{chaum} and a public append-only log. The public log makes it possible for a third party to verify that the user or mix cheated in the protocol when it is presented with the appropriate evidence, thus keeping all parties accountable. The system retains many of the benefits of the Mixcoin system, while also relaxing the constraint that the mix must be trusted to keep the input/output addess mappings of users hidden.

At this point, we have not been able to find any major flaws in our system, and we believe it holds promise. Further work will scrutinize the system against any attacks that have been proposed against mixing systems, and attempt to uncover any flaws in our system. Time constraints have prevented us from performing this analysis in this paper.

% Can use something like this to put references on a page
% by themselves when using endfloat and the captionsoff option.
\ifCLASSOPTIONcaptionsoff
\newpage
\fi



% trigger a \newpage just before the given reference
% number - used to balance the columns on the last page
% adjust value as needed - may need to be readjusted if
% the document is modified later
%\IEEEtriggeratref{8}
% The "triggered" command can be changed if desired:
%\IEEEtriggercmd{\enlargethispage{-5in}}

% references section

% can use a bibliography generated by BibTeX as a .bbl file
% BibTeX documentation can be easily obtained at:
% http://www.ctan.org/tex-archive/biblio/bibtex/contrib/doc/
% The IEEEtran BibTeX style support page is at:
% http://www.michaelshell.org/tex/ieeetran/bibtex/
\bibliographystyle{plain}
% argument is your BibTeX string definitions and bibliography database(s)
%\bibliography{IEEEabrv,../bib/paper}
%
% <OR> manually copy in the resultant .bbl file
% set second argument of \begin to the number of references
% (used to reserve space for the reference number labels box)

\bibliography{citations}

%TODO: add captions and name for this figure
\includepdf[pages={1}]{new_mixcoin_protocol.pdf}

% that's all folks
\end{document}












